package SetCoverProblem.SetCover;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/*
    区间覆盖：
    [x1, y1], [x2, y2], [x3, y3]……
    有n个区间，找出最多个数，两两不相交的区间个数
 */
public class SetCover {
    public static void main(String[] args) {

    }

    public static List<Interval> findMaxNumIntervals(List<Interval> intervals) {
        List<Interval> result = new ArrayList<>();
        Collections.sort(intervals);
        int right = 0;
        for (int i = 0; i < intervals.size(); i++) {
            Interval temp = intervals.get(i);
            if (temp.left >= right) {
                result.add(temp);
                right = temp.right;
            }
        }
        return result;
    }

    public static class Interval implements Comparable<Interval> {
        public int left;
        public int right;

        public Interval(int left, int right) {
            this.left = left;
            this.right = right;
        }

        @Override
        public int compareTo(Interval o) {
            //按照右端点进行排序
            return this.right - o.right;
        }
    }
}
